// 第一眼看这道题，感觉和贪心有点关系
// 用微扰法的方式看一下这道题有什么性质
// 对于每种选法组成的集合，分析相邻两个选择的特点：
//  先i再i+1：Ei + E(i + 1) - L(i + 1) * Si
// 先i+1再i: Ei + E(i + 1) - L(i) * S(i + 1)
// 从中就可以得出，如果想要得到能量最多的组合，必须要满足L(i + 1) * Si < L(i) * S(i + 1)
// 利用这种规则先进行贪心排序，然后再进行01背包问题
// 状态表示f[i][j]表示考虑前i个物品的情况下，所消耗时间恰好为j所能得到的最大能量
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = 110;

struct stone
{
    int s, e, l;
} Stones[M];
int f[N], n;

int main()
{
    int T;
    cin >> T;
    for (int C = 1; C <= T; ++C)
    {
        cin >> n;
        // 吃完所有能量石所需要的时间一定不超过这些时间的总和
        int m = 0;
        for (int i = 1; i <= n; ++i)
        {
            int s, e, l;
            cin >> s >> e >> l;
            Stones[i] = {s, e, l};
            m += s;
        }
        sort(Stones + 1, Stones + 1 + n, [](const stone &a, const stone &b)
             { return a.s * b.l < a.l * b.s; });
        // 由于要处理的是背包恰好的问题，所以要将各个值都初始化成负无穷
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        int res = 0;
        for (int i = 1; i <= n; ++i)
        {
            int s = Stones[i].s, e = Stones[i].e, l = Stones[i].l;
            for (int j = m; j >= s; --j)
            {
                f[j] = max(f[j], f[j - s] + max(0, e - l * (j - s)));
                res = max(res, f[j]);
            }
        }

        printf("Case #%d: %d\n", C, res);
    }
    return 0;
}